﻿#include<stdio.h>
#include<stdlib.h>
struct ListNode 
{
	int val;
	struct ListNode* next;
};
struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB)
{
	struct ListNode* curA = headA;
	struct ListNode* curB = headB;
	int countA = 0,countB = 0;
	while (curA)
	{
		curA = curA->next;
		countA++;
	}
	while (curB)
	{
		curB = curB->next;
		countB++;
	}
	if (curA != curB)
	{
		return NULL;
	}
	int k = abs(countA - countB);
	struct ListNode* longlist = headA;
	struct ListNode* shortlist = headB;
	if (countA < countB)
	{
		longlist = headB;
		shortlist = headA;
	}
	while (k--)
	{
		longlist = longlist->next;
	}
	while (longlist != shortlist)
	{
		longlist = longlist->next;
		shortlist = shortlist->next;
	}
	return longlist;
}
int main()
{
	struct ListNode* head = (struct ListNode*)malloc(sizeof(struct ListNode));
	head->val = 1;
	struct ListNode* node1 = (struct ListNode*)malloc(sizeof(struct ListNode));
	node1->val = 9;
	struct ListNode* node2 = (struct ListNode*)malloc(sizeof(struct ListNode));
	node2->val = 1;
	struct ListNode* node3 = (struct ListNode*)malloc(sizeof(struct ListNode));
	node3->val = 3;
	struct ListNode* node4 = (struct ListNode*)malloc(sizeof(struct ListNode));
	node4->val = 2;
	struct ListNode* node5 = (struct ListNode*)malloc(sizeof(struct ListNode));
	node5->val = 4;
	
	head->next = node1;
	node1->next = node2;
	node2->next = node4;
	node4->next = node5;
	node5->next = NULL;

	node3->next = node4;

	struct ListNode* headA = head;
	struct ListNode* headB = node3;
	struct ListNode* NodeMeet = getIntersectionNode(headA, headB);
	printf("%d", NodeMeet->val);
	return 0;
}